package com.wang;

/**
 * 分割等和子集
 * @author yandong
 */
public class CanPartitionSolution {
    public static boolean canPartition(int[] nums) {
        // 处理边界情况: 数组为空或长度为0, 则直接返回false
        if(nums == null || nums.length == 0) {
            return false;
        }
        int n = nums.length;  // 获取数组长度

        // 计算数组所有元素的总和
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        // 如果总和是奇数, 不可能分割成两个和相等的子集 --> 直接返回false
        if(sum % 2 != 0) {
            return false;
        }

        // 目标和: 每个子集需要达到的和
        int target = sum / 2;

        // dp数组定义: dp[j]表示在容量为j的背包中, 能装入的最大元素和
        // 这里的 背包容量 和 元素价值 都是元素本身的值
        int[] dp = new int[target + 1];

        // 遍历每个元素 (相当于0-1背包中的物品)
        for(int i = 0; i < n; i++) {
            // 从后往前遍历目标和 (避免重复使用同一个元素)
            // j从target开始,直到当前元素值 因为j < nums[i]时无法放入该元素
            for(int j = target; j >= nums[i]; j--) {
                // 状态转移方程：
                // 对于每个元素，有两种选择：放入或不放入背包
                // dp[j] = max(不放入当前元素保持原值, 放入当前元素后的值)
                // 放入当前元素后的值 = 当前元素值 + 剩余容量能达到的最大值
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                System.out.print("dp[" + j + "] = " + dp[j] +  " ");
            }
            System.out.println();

            // 剪枝优化: 如果在处理过程中已经找到符合条件的子集, 提前返回true
            // 这可以减少不必要的循环 提高效率
//            if(dp[target] == target) {
//                return true;
//            }
        }
        // 最终检查是否能达到目标和
        return dp[target] == target;
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums));
    }
}